package main

import (
	"container/list"
	"fmt"
)

/*
二叉搜索树的第k大节点
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。

示例 1:
输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4

示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4
*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//中序迭代遍历
//二叉树进行中序遍历后 就是从小到大排序
func kthLargest(root *TreeNode, k int) int {
	if root == nil {
		return 0
	}
	stack := list.New()
	var res []int
	for root != nil {
		stack.PushBack(root)
		root = root.Left
	}
	for stack.Len() > 0 {
		e := stack.Back()
		stack.Remove(e)
		node := e.Value.(*TreeNode)
		res = append(res, node.Val)
		node = node.Right
		for node != nil {
			stack.PushBack(node)
			node = node.Left
		}
	}
	return res[len(res)-k]
}

func main() {
	A := &TreeNode{Val: 3}
	A.Left = &TreeNode{
		Val: 1,
		Left: &TreeNode{
			Val: 2,
		},
	}
	A.Right = &TreeNode{Val: 4}
	fmt.Println(kthLargest(A, 1))
}
